package linkedList;

import java.util.*;

/**
 * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 *
 * 示例：
 *
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 */
public class Solution4 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        List<Integer> list = new ArrayList<Integer>();
        if(l1 != null){
            while(l1 != null){
                list.add(l1.val);
                l1 = l1.next;
            }
        }

        if(l2 != null){
            while(l2 != null){
                list.add(l2.val);
                l2 = l2.next;
            }
        }

        Collections.sort(list, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });

        ListNode result = null;
        if(list.size() > 0){
            result = new ListNode(list.get(0));


            ListNode cur = result;
            for(int i = 1;i < list.size(); i++){
                cur.next = new ListNode(list.get(i));
                cur = cur.next;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,4};
        ListNode l1 = new ListNode(arr);
        System.out.println(l1);
        int[] arr2 = {1,3,4};
        ListNode l2 = new ListNode(arr2);
        System.out.println(l2);
        Solution4 solution = new Solution4();
        ListNode res  = solution.mergeTwoLists(l1,l2);
        System.out.println(res);
    }
}
